/*
 * contrib/intarray/_int_bool.c
 */
#include "postgres.h"

#include "_int.h"
#include "miscadmin.h"
#include "utils/builtins.h"

PG_FUNCTION_INFO_V1(bqarr_in);
PG_FUNCTION_INFO_V1(bqarr_out);
PG_FUNCTION_INFO_V1(boolop);
PG_FUNCTION_INFO_V1(rboolop);
PG_FUNCTION_INFO_V1(querytree);


/* 解析器的状态 */
#define WAITOPERAND 1
#define WAITENDOPERAND	2
#define WAITOPERATOR	3

/*
 * 查询树的节点，也用于
 * 在解析器中存储波兰表示法
 */
typedef struct NODE
{
	int32		type;
	int32		val;
	struct NODE *next;
} NODE;

typedef struct
{
	char	   *buf;
	int32		state;
	int32		count;
	/* 列表中的逆波兰表示法（用于临时使用） */
	NODE	   *str;
	/* 字符串中的数字 */
	int32		num;
} WORKSTATE;

/*
 * 从查询字符串中获取标记
 */
static int32 fc_gettoken(WORKSTATE *fc_state, int32 *fc_val)
{
	char		fc_nnn[16];
	int			fc_innn;

	*fc_val = 0;					/* 默认结果 */

	fc_innn = 0;
	while (1)
	{
		if (fc_innn >= sizeof(fc_nnn))
			return ERR;			/* 缓冲区溢出 => 语法错误 */
		switch (fc_state->state)
		{
			case WAITOPERAND:
				fc_innn = 0;
				if ((*(fc_state->buf) >= '0' && *(fc_state->buf) <= '9') ||
					*(fc_state->buf) == '-')
				{
					fc_state->state = WAITENDOPERAND;
					fc_nnn[fc_innn++] = *(fc_state->buf);
				}
				else if (*(fc_state->buf) == '!')
				{
					(fc_state->buf)++;
					*fc_val = (int32) '!';
					return OPR;
				}
				else if (*(fc_state->buf) == '(')
				{
					fc_state->count++;
					(fc_state->buf)++;
					return OPEN;
				}
				else if (*(fc_state->buf) != ' ')
					return ERR;
				break;
			case WAITENDOPERAND:
				if (*(fc_state->buf) >= '0' && *(fc_state->buf) <= '9')
				{
					fc_nnn[fc_innn++] = *(fc_state->buf);
				}
				else
				{
					long		fc_lval;

					fc_nnn[fc_innn] = '\0';
					errno = 0;
					fc_lval = strtol(fc_nnn, NULL, 0);
					*fc_val = (int32) fc_lval;
					if (errno != 0 || (long) *fc_val != fc_lval)
						return ERR;
					fc_state->state = WAITOPERATOR;
					return (fc_state->count && *(fc_state->buf) == '\0')
						? ERR : VAL;
				}
				break;
			case WAITOPERATOR:
				if (*(fc_state->buf) == '&' || *(fc_state->buf) == '|')
				{
					fc_state->state = WAITOPERAND;
					*fc_val = (int32) *(fc_state->buf);
					(fc_state->buf)++;
					return OPR;
				}
				else if (*(fc_state->buf) == ')')
				{
					(fc_state->buf)++;
					fc_state->count--;
					return (fc_state->count < 0) ? ERR : CLOSE;
				}
				else if (*(fc_state->buf) == '\0')
					return (fc_state->count) ? ERR : END;
				else if (*(fc_state->buf) != ' ')
					return ERR;
				break;
			default:
				return ERR;
				break;
		}
		(fc_state->buf)++;
	}
}

/*
 * 在波兰表示法的逆视图中推入新的元素
 */
static void fc_pushquery(WORKSTATE *fc_state, int32 fc_type, int32 fc_val)
{
	NODE	   *fc_tmp = (NODE *) palloc(sizeof(NODE));

	fc_tmp->type = fc_type;
	fc_tmp->val = fc_val;
	fc_tmp->next = fc_state->str;
	fc_state->str = fc_tmp;
	fc_state->num++;
}

#define STACKDEPTH	16

/*
 * 构建查询的波兰表示法
 */
static int32 fc_makepol(WORKSTATE *fc_state)
{
	int32		fc_val,
				fc_type;
	int32		fc_stack[STACKDEPTH];
	int32		fc_lenstack = 0;

	/* 由于这个函数递归，可能会导致栈溢出 */
	check_stack_depth();

	while ((fc_type = fc_gettoken(fc_state, &fc_val)) != END)
	{
		switch (fc_type)
		{
			case VAL:
				fc_pushquery(fc_state, fc_type, fc_val);
				while (fc_lenstack && (fc_stack[fc_lenstack - 1] == (int32) '&' ||
									fc_stack[fc_lenstack - 1] == (int32) '!'))
				{
					fc_lenstack--;
					fc_pushquery(fc_state, OPR, fc_stack[fc_lenstack]);
				}
				break;
			case OPR:
				if (fc_lenstack && fc_val == (int32) '|')
					fc_pushquery(fc_state, OPR, fc_val);
				else
				{
					if (fc_lenstack == STACKDEPTH)
#ifdef FDD //cppcheck
					{
#endif
						ereport(ERROR,
								(errcode(ERRCODE_STATEMENT_TOO_COMPLEX),
								 errmsg("statement too complex")));
#ifdef FDD //cppcheck
						return ERR;
					}
#endif
					fc_stack[fc_lenstack] = fc_val;
					fc_lenstack++;
				}
				break;
			case OPEN:
				if (fc_makepol(fc_state) == ERR)
					return ERR;
				while (fc_lenstack && (fc_stack[fc_lenstack - 1] == (int32) '&' ||
									fc_stack[fc_lenstack - 1] == (int32) '!'))
				{
					fc_lenstack--;
					fc_pushquery(fc_state, OPR, fc_stack[fc_lenstack]);
				}
				break;
			case CLOSE:
				while (fc_lenstack)
				{
					fc_lenstack--;
					fc_pushquery(fc_state, OPR, fc_stack[fc_lenstack]);
				};
				return END;
				break;
			case ERR:
			default:
				ereport(ERROR,
						(errcode(ERRCODE_SYNTAX_ERROR),
						 errmsg("syntax error")));
				return ERR;
		}
	}

	while (fc_lenstack)
	{
		fc_lenstack--;
		fc_pushquery(fc_state, OPR, fc_stack[fc_lenstack]);
	};
	return END;
}

typedef struct
{
	int32	   *arrb;
	int32	   *arre;
} CHKVAL;

/*
 * 在（已排序）数组中是否有值 'val' ?
 */
static bool fc_checkcondition_arr(void *fc_checkval, ITEM *fc_item, void *fc_options)
{
	int32	   *fc_StopLow = ((CHKVAL *) fc_checkval)->arrb;
	int32	   *fc_StopHigh = ((CHKVAL *) fc_checkval)->arre;
	int32	   *fc_StopMiddle;

	/* 循环不变式： StopLow <= val < StopHigh */

	while (fc_StopLow < fc_StopHigh)
	{
		fc_StopMiddle = fc_StopLow + (fc_StopHigh - fc_StopLow) / 2;
		if (*fc_StopMiddle == fc_item->val)
			return true;
		else if (*fc_StopMiddle < fc_item->val)
			fc_StopLow = fc_StopMiddle + 1;
		else
			fc_StopHigh = fc_StopMiddle;
	}
	return false;
}

static bool fc_checkcondition_bit(void *fc_checkval, ITEM *fc_item, void *fc_siglen)
{
	return GETBIT(fc_checkval, HASHVAL(fc_item->val, (int) (intptr_t) fc_siglen));
}

/*
 * 评估布尔表达式，使用 chkcond() 测试基本情况
 */
static bool fc_execute(ITEM *fc_curitem, void *fc_checkval, void *fc_options, bool fc_calcnot,
		bool (*fc_chkcond) (void *checkval, ITEM *item, void *options))
{
	/* 由于这个函数递归，可能会导致栈溢出 */
	check_stack_depth();

	if (fc_curitem->type == VAL)
		return (*fc_chkcond) (fc_checkval, fc_curitem, fc_options);
	else if (fc_curitem->val == (int32) '!')
	{
		return fc_calcnot ?
			((fc_execute(fc_curitem - 1, fc_checkval, fc_options, fc_calcnot, fc_chkcond)) ? false : true)
			: true;
	}
	else if (fc_curitem->val == (int32) '&')
	{
		if (fc_execute(fc_curitem + fc_curitem->left, fc_checkval, fc_options, fc_calcnot, fc_chkcond))
			return fc_execute(fc_curitem - 1, fc_checkval, fc_options, fc_calcnot, fc_chkcond);
		else
			return false;
	}
	else
	{							/* |-操作符 */
		if (fc_execute(fc_curitem + fc_curitem->left, fc_checkval, fc_options, fc_calcnot, fc_chkcond))
			return true;
		else
			return fc_execute(fc_curitem - 1, fc_checkval, fc_options, fc_calcnot, fc_chkcond);
	}
}

/*
 * signconsistent 和 execconsistent 由 *_consistent 调用
 */
bool signconsistent(QUERYTYPE *fc_query, BITVECP fc_sign, int fc_siglen, bool fc_calcnot)
{
	return fc_execute(GETQUERY(fc_query) + fc_query->size - 1,
				   (void *) fc_sign, (void *) (intptr_t) fc_siglen, fc_calcnot,
				   fc_checkcondition_bit);
}

/* 数组必须是已排序的！ */
bool execconsistent(QUERYTYPE *fc_query, ArrayType *fc_array, bool fc_calcnot)
{
	CHKVAL		fc_chkval;

	CHECKARRVALID(fc_array);
	fc_chkval.arrb = ARRPTR(fc_array);
	fc_chkval.arre = fc_chkval.arrb + ARRNELEMS(fc_array);
	return fc_execute(GETQUERY(fc_query) + fc_query->size - 1,
				   (void *) &fc_chkval, NULL, fc_calcnot,
				   fc_checkcondition_arr);
}

typedef struct
{
	ITEM	   *first;
	bool	   *mapped_check;
} GinChkVal;

static bool fc_checkcondition_gin(void *fc_checkval, ITEM *fc_item, void *fc_options)
{
	GinChkVal  *fc_gcv = (GinChkVal *) fc_checkval;

	return fc_gcv->mapped_check[fc_item - fc_gcv->first];
}

bool gin_bool_consistent(QUERYTYPE *fc_query, bool *fc_check)
{
	GinChkVal	fc_gcv;
	ITEM	   *fc_items = GETQUERY(fc_query);
	int			fc_i,
				fc_j = 0;

	if (fc_query->size <= 0)
		return false;

	/*
	 * 为 checkcondition_gin 设置数据。这必须与查询
	 * 提取代码中的 ginint4_queryextract 一致。
	 */
	fc_gcv.first = fc_items;
	fc_gcv.mapped_check = (bool *) palloc(sizeof(bool) * fc_query->size);
	for (fc_i = 0; fc_i < fc_query->size; fc_i++)
	{
		if (fc_items[fc_i].type == VAL)
			fc_gcv.mapped_check[fc_i] = fc_check[fc_j++];
	}

	return fc_execute(GETQUERY(fc_query) + fc_query->size - 1,
				   (void *) &fc_gcv, NULL, true,
				   fc_checkcondition_gin);
}

static bool fc_contains_required_value(ITEM *fc_curitem)
{
	/* 由于这个函数递归，可能会导致栈溢出 */
	check_stack_depth();

	if (fc_curitem->type == VAL)
		return true;
	else if (fc_curitem->val == (int32) '!')
	{
		/*
		 * 假设在 NOT 下的一切都是非必需的。在某些嵌套 NOT 的情况下，
		 * 我们可以证明存在一个必需的值，但这似乎不值得麻烦。
		 */
		return false;
	}
	else if (fc_curitem->val == (int32) '&')
	{
		/* 如果任一侧有必需的值，我们就好了 */
		if (fc_contains_required_value(fc_curitem + fc_curitem->left))
			return true;
		else
			return fc_contains_required_value(fc_curitem - 1);
	}
	else
	{							/* |-操作符 */
		/* 双方必须都有必需的值 */
		if (fc_contains_required_value(fc_curitem + fc_curitem->left))
			return fc_contains_required_value(fc_curitem - 1);
		else
			return false;
	}
}

bool query_has_required_values(QUERYTYPE *fc_query)
{
	if (fc_query->size <= 0)
		return false;
	return fc_contains_required_value(GETQUERY(fc_query) + fc_query->size - 1);
}

/*
 * 布尔操作
 */
Datum rboolop(PG_FUNCTION_ARGS)
{
	/* 只需反转操作数 */
	return DirectFunctionCall2(boolop,
							   PG_GETARG_DATUM(1),
							   PG_GETARG_DATUM(0));
}

Datum boolop(PG_FUNCTION_ARGS)
{
	ArrayType  *fc_val = PG_GETARG_ARRAYTYPE_P_COPY(0);
	QUERYTYPE  *fc_query = PG_GETARG_QUERYTYPE_P(1);
	CHKVAL		fc_chkval;
	bool		fc_result;

	CHECKARRVALID(fc_val);
	PREPAREARR(fc_val);
	fc_chkval.arrb = ARRPTR(fc_val);
	fc_chkval.arre = fc_chkval.arrb + ARRNELEMS(fc_val);
	fc_result = fc_execute(GETQUERY(fc_query) + fc_query->size - 1,
					 &fc_chkval, NULL, true,
					 fc_checkcondition_arr);
	pfree(fc_val);

	PG_FREE_IF_COPY(fc_query, 1);
	PG_RETURN_BOOL(fc_result);
}

static void fc_findoprnd(ITEM *fc_ptr, int32 *fc_pos)
{
	/* 由于这个函数递归，它可能导致栈溢出。 */
	check_stack_depth();

#ifdef BS_DEBUG
	elog(DEBUG3, (fc_ptr[*fc_pos].type == OPR) ?
		 "%d  %c" : "%d  %d", *fc_pos, fc_ptr[*fc_pos].val);
#endif
	if (fc_ptr[*fc_pos].type == VAL)
	{
		fc_ptr[*fc_pos].left = 0;
		(*fc_pos)--;
	}
	else if (fc_ptr[*fc_pos].val == (int32) '!')
	{
		fc_ptr[*fc_pos].left = -1;
		(*fc_pos)--;
		fc_findoprnd(fc_ptr, fc_pos);
	}
	else
	{
		ITEM	   *fc_curitem = &fc_ptr[*fc_pos];
		int32		fc_tmp = *fc_pos;

		(*fc_pos)--;
		fc_findoprnd(fc_ptr, fc_pos);
		fc_curitem->left = *fc_pos - fc_tmp;
		fc_findoprnd(fc_ptr, fc_pos);
	}
}


/*
 * 输入
 */
Datum bqarr_in(PG_FUNCTION_ARGS)
{
	char	   *fc_buf = (char *) PG_GETARG_POINTER(0);
	WORKSTATE	fc_state;
	int32		fc_i;
	QUERYTYPE  *fc_query;
	int32		fc_commonlen;
	ITEM	   *fc_ptr;
	NODE	   *fc_tmp;
	int32		fc_pos = 0;

#ifdef BS_DEBUG
	StringInfoData fc_pbuf;
#endif

	fc_state.buf = fc_buf;
	fc_state.state = WAITOPERAND;
	fc_state.count = 0;
	fc_state.num = 0;
	fc_state.str = NULL;

	/* 生成波兰表示法（后缀，但顺序反转） */
	fc_makepol(&fc_state);
	if (!fc_state.num)
		ereport(ERROR,
				(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
				 errmsg("empty query")));

	if (fc_state.num > QUERYTYPEMAXITEMS)
		ereport(ERROR,
				(errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
				 errmsg("number of query items (%d) exceeds the maximum allowed (%d)",
						fc_state.num, (int) QUERYTYPEMAXITEMS)));
	fc_commonlen = COMPUTESIZE(fc_state.num);

	fc_query = (QUERYTYPE *) palloc(fc_commonlen);
	SET_VARSIZE(fc_query, fc_commonlen);
	fc_query->size = fc_state.num;
	fc_ptr = GETQUERY(fc_query);

	for (fc_i = fc_state.num - 1; fc_i >= 0; fc_i--)
	{
		fc_ptr[fc_i].type = fc_state.str->type;
		fc_ptr[fc_i].val = fc_state.str->val;
		fc_tmp = fc_state.str->next;
		pfree(fc_state.str);
		fc_state.str = fc_tmp;
	}

	fc_pos = fc_query->size - 1;
	fc_findoprnd(fc_ptr, &fc_pos);
#ifdef BS_DEBUG
	initStringInfo(&fc_pbuf);
	for (fc_i = 0; fc_i < fc_query->size; fc_i++)
	{
		if (fc_ptr[fc_i].type == OPR)
			appendStringInfo(&fc_pbuf, "%c(%d) ", fc_ptr[fc_i].val, fc_ptr[fc_i].left);
		else
			appendStringInfo(&fc_pbuf, "%d ", fc_ptr[fc_i].val);
	}
	elog(DEBUG3, "POR: %s", fc_pbuf.data);
	pfree(fc_pbuf.data);
#endif

	PG_RETURN_POINTER(fc_query);
}


/*
 * 输出函数
 */
typedef struct
{
	ITEM	   *curpol;
	char	   *buf;
	char	   *cur;
	int32		buflen;
} INFIX;

#define RESIZEBUF(inf,addsize) while( ( (inf)->cur - (inf)->buf ) + (addsize) + 1 >= (inf)->buflen ) { \
	int32 fc_len = inf->cur - inf->buf; \
	inf->buflen *= 2; \
	inf->buf = (char*) repalloc( (void*)inf->buf, inf->buflen ); \
	inf->cur = inf->buf + fc_len; \
}

static void fc_infix(INFIX *fc_in, bool fc_first)
{
	/* 由于这个函数递归，它可能导致栈溢出。 */
	check_stack_depth();

	if (fc_in->curpol->type == VAL)
	{
		RESIZEBUF(fc_in, 11);
		sprintf(fc_in->cur, "%d", fc_in->curpol->val);
		fc_in->cur = strchr(fc_in->cur, '\0');
		fc_in->curpol--;
	}
	else if (fc_in->curpol->val == (int32) '!')
	{
		bool		fc_isopr = false;

		RESIZEBUF(fc_in, 1);
		*(fc_in->cur) = '!';
		fc_in->cur++;
		*(fc_in->cur) = '\0';
		fc_in->curpol--;
		if (fc_in->curpol->type == OPR)
		{
			fc_isopr = true;
			RESIZEBUF(fc_in, 2);
			sprintf(fc_in->cur, "( ");
			fc_in->cur = strchr(fc_in->cur, '\0');
		}
		fc_infix(fc_in, fc_isopr);
		if (fc_isopr)
		{
			RESIZEBUF(fc_in, 2);
			sprintf(fc_in->cur, " )");
			fc_in->cur = strchr(fc_in->cur, '\0');
		}
	}
	else
	{
		int32		fc_op = fc_in->curpol->val;
		INFIX		fc_nrm;

		fc_in->curpol--;
		if (fc_op == (int32) '|' && !fc_first)
		{
			RESIZEBUF(fc_in, 2);
			sprintf(fc_in->cur, "( ");
			fc_in->cur = strchr(fc_in->cur, '\0');
		}

		fc_nrm.curpol = fc_in->curpol;
		fc_nrm.buflen = 16;
		fc_nrm.cur = fc_nrm.buf = (char *) palloc(sizeof(char) * fc_nrm.buflen);

		/* 获取右操作数 */
		fc_infix(&fc_nrm, false);

		/* 获取并打印左操作数 */
		fc_in->curpol = fc_nrm.curpol;
		fc_infix(fc_in, false);

		/* 打印操作符和右操作数 */
		RESIZEBUF(fc_in, 3 + (fc_nrm.cur - fc_nrm.buf));
		sprintf(fc_in->cur, " %c %s", fc_op, fc_nrm.buf);
		fc_in->cur = strchr(fc_in->cur, '\0');
		pfree(fc_nrm.buf);

		if (fc_op == (int32) '|' && !fc_first)
		{
			RESIZEBUF(fc_in, 2);
			sprintf(fc_in->cur, " )");
			fc_in->cur = strchr(fc_in->cur, '\0');
		}
	}
}


Datum bqarr_out(PG_FUNCTION_ARGS)
{
	QUERYTYPE  *fc_query = PG_GETARG_QUERYTYPE_P(0);
	INFIX		fc_nrm;

	if (fc_query->size == 0)
		ereport(ERROR,
				(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
				 errmsg("empty query")));

	fc_nrm.curpol = GETQUERY(fc_query) + fc_query->size - 1;
	fc_nrm.buflen = 32;
	fc_nrm.cur = fc_nrm.buf = (char *) palloc(sizeof(char) * fc_nrm.buflen);
	*(fc_nrm.cur) = '\0';
	fc_infix(&fc_nrm, true);

	PG_FREE_IF_COPY(fc_query, 0);
	PG_RETURN_POINTER(fc_nrm.buf);
}


/* 对于一个根本错误的算法来说，无用的旧“调试”函数 */
Datum querytree(PG_FUNCTION_ARGS)
{
	elog(ERROR, "querytree is no longer implemented");
	PG_RETURN_NULL();
}
